#include <stack>
#include <queue>
using namespace std;
/*
 * @lc app=leetcode.cn id=101 lang=cpp
 *
 * [101] 对称二叉树
 */
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    // 递归的方式
    // bool isSymmetric(TreeNode* root) {
    //     if (!root) return true;
    //     return isSymmetricTwo(root->left, root->right);
    // }

    // bool isSymmetricTwo(TreeNode *l, TreeNode *r) {
    //     if (!l && !r) return true;
    //     if (!l || !r) return false;
    //     if (l->val != r->val) return false;
    //     return isSymmetricTwo(l->left, r->right) && isSymmetricTwo(l->right, r->left);
    // }

    // bool isSymmetric(TreeNode* root) {
    //     if (!root) return true;
    //     stack<TreeNode*> ls; stack<TreeNode*> rs;
    //     TreeNode *l = root->left, *r = root->right;
    //     while ((!ls.empty() && !rs.empty()) || (l && r)) {
    //         while (l) {
    //             ls.push(l); l = l->left;
    //         }
    //         while (r) {
    //             rs.push(r); r = r->right;
    //         }
    //         if (rs.size() != ls.size()) return false;
    //         l = ls.top(); ls.pop();
    //         r = rs.top(); rs.pop();
    //         if (!l && !r) continue;
    //         if (!l || !r) return false;
    //         if (l->val != r->val) return false;
    //         l = l->right; r = r->left;
    //     }
    //     if (!l && !r) return true;
    //     if (!l || !r) return false;
    //     if (l->val != r->val) return false;
    //     return true;
    // }

    bool isSymmetric(TreeNode* root) {
        queue<TreeNode*> q;
        if (!root) return true;
        q.push(root->left); q.push(root->right);
        while (!q.empty()) {
            auto l = q.front(); q.pop();
            auto r = q.front(); q.pop();
            if (!l && !r) continue;
            if (!l || !r) return false;
            if (l->val != r->val) return false;
            q.push(l->right); q.push(r->left);
            q.push(l->left); q.push(r->right);
        }
        return true;
    }

};
// @lc code=end

